home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_300 / 308_01 / dbl_list.cpp < prev    next >
C/C++ Source or Header  |  1990-09-19  |  6KB  |  313 lines
  1.  
  2. /*
  3.     TITLE:        DoubleList;
  4.     DESCRIPTION:    "C++ doubly-linked list    object;
  5.     VERSION:    1.0;
  6.     DATE:        9/7/90;
  7.     COMPILERS:    Borland    Turbo C++ V.1.0;
  8.     KEYWORDS:    C++ linked list    object;
  9.     FILENAME:    Dbl_List.cpp;
  10.     SEE-ALSO:    Dbl_List.hpp, BaseList.hpp;
  11.  
  12.     AUTHOR:        Michael    Kelly
  13.             254 Gold St. Boston Ma.    02127
  14.             Copyright 1990;
  15.  
  16.     COPYRIGHT:    This code may not be commercially distributed
  17.             without prior arrangement with the author.  It
  18.             may be used by programmers, without royalty, for
  19.             their personal programs and for "one of a kind"
  20.             or "custom" applications, provided that said
  21.             programmers assume all liability concerning
  22.             same.
  23. */
  24.  
  25.  
  26.  //            ----------<    DoubleList Object >----------
  27.  
  28. #include <stdlib.h>
  29. #include "dbl_list.hpp"
  30.  
  31.  
  32. //        ----------< Public Methods >----------
  33.  
  34.  
  35. // destructor
  36.  
  37. DoubleList::~DoubleList(void)
  38. {
  39.     while(delete_item())
  40.     ;    // empty loop -- deletes every link in list
  41.  
  42.     if(lerror == EMPTY_LIST)
  43.     lerror = OK;
  44. }
  45.  
  46.  
  47. // add a new item to list at Place place
  48.  
  49. Boolean    DoubleList::add_item(void *item, size_t    itemsize, Place    place)
  50. {
  51.     Entry *newentry;
  52.     DoubleLink *newlink;
  53.     void *ptr =    item;    // avoids empty    char array being flagged as NULL ptr
  54.  
  55.     lerror = OK;
  56.  
  57.     if(! ptr)
  58.     lerror = NULL_PTR;
  59.     if(itemsize    < 1)
  60.     lerror = INV_SIZE;
  61.  
  62.     if(lerror)
  63.     return False;
  64.  
  65.     if(! (newlink = new    DoubleLink))  {
  66.     lerror = NO_MEM;
  67.     return False;
  68.     }
  69.     if(! (newentry = new Entry))  {
  70.     delete newlink;
  71.     lerror = NO_MEM;
  72.     return False;
  73.     }
  74.     if(! (newentry->item = new char[itemsize]))     {
  75.     delete newentry;
  76.     delete newlink;
  77.     lerror = NO_MEM;
  78.     return False;
  79.     }
  80.  
  81.     memmove(newentry->item, item, itemsize);
  82.     newentry->itemsize = itemsize;
  83.     newlink->entry = newentry;
  84.  
  85.     if(! entries)  {                // adding to empty list
  86.     newlink->Next =    newlink->Prev =    NULL;
  87.     First =    Last = Current = newlink;
  88.     entries    = 1;
  89.     return True;
  90.     }
  91.  
  92.     if(place ==    FirstPlace)  {
  93.     newlink->Prev =    NULL;
  94.     newlink->Next =    First;
  95.     First->Prev = newlink;
  96.     First =    newlink;
  97.     }
  98.     else if(place == LastPlace    ||  Current == Last)  {
  99.     newlink->Next =    NULL;
  100.     newlink->Prev =    Last;
  101.     Last->Next = newlink;
  102.     Last = newlink;
  103.     }
  104.     else  {
  105.     newlink->Next =    Current->Next;
  106.     newlink->Prev =    Current;
  107.     Current->Next->Prev = newlink;
  108.     Current->Next =    newlink;
  109.     }
  110.  
  111.     Current = newlink;
  112.     entries++;
  113.     return True;
  114. }
  115.  
  116.  
  117. // delete the current item from    the list
  118.  
  119. Boolean    DoubleList::delete_item(void)
  120. {
  121.     lerror = OK;
  122.  
  123.     if(! entries)
  124.     lerror = EMPTY_LIST;
  125.     if(entries    &&  ! Current)
  126.     lerror = NULL_PTR;
  127.  
  128.     if(lerror)
  129.     return False;
  130.  
  131.     delete Current->entry->item;
  132.     delete Current->entry;
  133.  
  134.     if(entries == 1)  {           // deleting the only item in the    list
  135.     delete First;
  136.     First =    Last = Current = NULL;
  137.     entries    = 0;
  138.     return True;
  139.     }
  140.  
  141.     if(Current == First)  {
  142.     First =    First->Next;
  143.     First->Prev = NULL;
  144.     }
  145.     else if(Current == Last)  {
  146.     Last = Last->Prev;
  147.     Last->Next = NULL;
  148.     }
  149.     else  {
  150.     Current->Prev->Next = Current->Next;
  151.     Current->Next->Prev = Current->Prev;
  152.     }
  153.  
  154.     delete Current;
  155.     Current = First;
  156.     entries--;
  157.     return True;
  158. }
  159.  
  160.  
  161. // copy    the current item in the    list to    buffer
  162.  
  163. Boolean    DoubleList::get_item(void *itembuf)
  164. {
  165.     void *ptr =    itembuf;
  166.  
  167.     lerror = OK;
  168.  
  169.     if(! entries)
  170.     lerror = EMPTY_LIST;
  171.     if(entries    &&  (! ptr  ||    ! Current))
  172.     lerror = NULL_PTR;
  173.  
  174.     if(lerror)
  175.     return False;
  176.  
  177.     memmove(itembuf, Current->entry->item, Current->entry->itemsize);
  178.     return True;
  179. }
  180.  
  181.  
  182. // compare item1 with current item in list
  183.  
  184. int DoubleList::compare_item(void *item1)
  185. {
  186.     void *ptr =    item1;
  187.  
  188.     lerror = OK;
  189.  
  190.     if(! entries)
  191.     lerror = EMPTY_LIST;
  192.     if(entries    &&  (! Current    ||  ! ptr))
  193.     lerror = NULL_PTR;
  194.  
  195.     if(lerror)
  196.     return 0;
  197.  
  198.     return compare(item1, Current->entry->item);
  199. }
  200.  
  201.  
  202. // search the list for item that matches item1
  203.  
  204. Boolean    DoubleList::find_item(void *item1)
  205. {
  206.     int    dif;
  207.     void *ptr =    item1;
  208.  
  209.     lerror = OK;
  210.  
  211.  
  212.     if(! entries)
  213.     lerror = EMPTY_LIST;
  214.     if(entries    &&  (! first() || ! ptr))
  215.     lerror = NULL_PTR;
  216.  
  217.     if(lerror)
  218.     return False;
  219.  
  220.     while((dif = compare_item(item1))  &&  DoubleList::next())
  221.     ;    // empty loop -- sequential search for match
  222.  
  223.     return (Boolean) !dif; // logically    convert    integer    result to boolean
  224. }
  225.  
  226.  
  227. // replace the "current" item in list with newitem
  228.  
  229. Boolean    DoubleList::replace_item(void *newitem,    size_t newsize)
  230. {
  231.     void *ptr =    newitem;
  232.     void *tmp;
  233.  
  234.     lerror = OK;
  235.  
  236.     if(! entries)
  237.     lerror = EMPTY_LIST;
  238.     if(entries    &&  ! ptr)
  239.     lerror = NULL_PTR;
  240.     if(! newsize)
  241.     lerror = INV_SIZE;
  242.  
  243.     if(lerror)
  244.     return False;
  245.  
  246.     if(! (tmp =    new char[newsize]))  {
  247.     lerror = NO_MEM;
  248.     return False;
  249.     }
  250.     delete Current->entry->item;
  251.     Current->entry->item = tmp;
  252.     Current->entry->itemsize = newsize;
  253.     memmove(Current->entry->item, newitem, newsize);
  254.     return True;
  255. }
  256.  
  257. /*
  258.  *  sort() uses    compare() function indirectly through dcompare()
  259.  *  with host qsort() function to sort the DoubleList
  260.  *
  261.  *  returns:        0    if DoubleList is empty or not enough memory
  262.  *            for sorting table
  263.  *
  264.  *            sets lerror to error code
  265.  *
  266.  *
  267.  *            1    if sort    completed
  268.  *
  269.  *            first item in DoubleList is "current" item
  270.  */
  271. Boolean    DoubleList::sort(void)
  272. {
  273.     Entry **entry_array;
  274.     Entry **save_array_base;
  275.  
  276.     lerror = (entries >    0) ? OK    : EMPTY_LIST;
  277.  
  278.     if(entries < 2)
  279.     return (Boolean) entries;
  280.  
  281.     if(! (save_array_base =
  282.     (Entry **) new char[entries * sizeof(Entry *)]))  {
  283.         lerror = NO_MEM;
  284.         return False;
  285.     }
  286.     entry_array    = save_array_base;
  287.  
  288.     Current = First;
  289.  
  290.     do    {
  291.  
  292.     *entry_array++ = Current->entry;
  293.     }
  294.     while(Current = Current->Next);
  295.  
  296.     Current = First;
  297.     entry_array    = save_array_base;
  298.     this_list =    this;
  299.     qsort(entry_array, entries,    sizeof entry_array[0], qcompare);
  300.  
  301.     do    {
  302.  
  303.     Current->entry = *entry_array++;
  304.     }
  305.     while(Current = Current->Next);
  306.  
  307.     Current = First;
  308.     delete save_array_base;
  309.     return True;
  310. }
  311.  
  312.  
  313.